package com.south.base.utils;

import lombok.Data;

import java.util.*;

/**
 * 回文计算工具
 *
 * @author Administrator
 */
public class PalindromeUtil {
    /**
     * 内部最长的回文
     *
     * @param s
     * @return
     */
    public static String longestInsidePalindrome(String s) {
        Index index = new Index();
        if (s.length() < 2) {
            return s;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            PalindromeHelper(s, i, i, index);
            PalindromeHelper(s, i, i + 1, index);
        }
        return s.substring(index.getIndex(), index.getIndex() + index.getLen());
    }

    /**
     * 遍历从l开始到字符串最长回文长度
     *
     * @param s
     * @param l
     * @param r
     * @param index
     */
    private static void PalindromeHelper(String s, int l, int r, Index index) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        if (index.getLen() < r - l - 1) {
            index.setIndex(l + 1);
            index.setLen(r - l - 1);
        }
    }

    /**
     * 所能组成最长的回文长度
     *
     * @param s
     * @return
     */
    public static int longestPalindrome(String s) {
        if (s.length() == 0) {
            return 0;
        }
        // 用于存放字符
        Set<Character> hashSet = new HashSet<>();
        char[] chars = s.toCharArray();
        int count = 0;
        for (int i = 0; i < chars.length; i++) {
            if (!hashSet.contains(chars[i])) {
                // 如果hashset没有该字符就保存进去
                hashSet.add(chars[i]);
            } else {
                // 如果有,就让count++（说明找到了一个成对的字符），然后把该字符移除
                hashSet.remove(chars[i]);
                count++;
            }
        }
        return hashSet.isEmpty() ? count * 2 : count * 2 + 1;
    }

    public static int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                } else {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        return f[0][n - 1];
    }

    /**
     * 判断字符串是否是回文
     * 只考虑字母和数字字符，可以忽略字母的大小写。
     *
     * @param s
     * @return
     */
    public static boolean isLetterOrDigitPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (!Character.isLetterOrDigit(s.charAt(l))) {
                l++;
                continue;
            }
            if (!Character.isLetterOrDigit(s.charAt(r))) {
                r--;
                continue;
            }
            // 判断二者是否相等
            if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }

    /**
     * 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
     *
     * @param s
     * @return
     */
    public static boolean validPalindrome(String s) {
        if (s.length() == 0) {
            return true;
        }
        int l = 0, r = s.length() - 1;
        boolean b = true;
        while (l < r) {
            // 判断二者是否相等
            if (s.charAt(l) != s.charAt(r)) {
                b = false;
                break;
            }
            l++;
            r--;
        }
        if (!b) {
            b = isPalindrome(s, l + 1, r);
        }
        if (!b) {
            b = isPalindrome(s, l, r - 1);
        }
        return b;
    }

    /**
     * 判断字符串是否是回文
     *
     * @param s
     * @return
     */
    public static boolean isPalindrome(String s) {
        if (s.length() == 0) {
            return true;
        }
        return isPalindrome(s, 0, s.length() - 1);
    }

    public static boolean isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }

    public static boolean isPalindrome2(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        return isPalindrome(Integer.toString(x));
    }

    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        ListNode pre = head, prepre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            pre.next = prepre;
            prepre = pre;
        }
        if (fast != null) {
            slow = slow.next;
        }
        while (pre != null && slow != null) {
            if (pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }

    public static boolean isPalindrome(String s, int left, int right) {
        int len = right - left + 1;
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(left + i) != s.charAt(right - i)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
     * 说明：本题中，我们将空字符串定义为有效的回文串。
     */
    public boolean isPalindromeIgnoreCase(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (!isChar(s.charAt(left))) {
                left++;
            } else if (!isChar(s.charAt(right))) {
                right--;
            } else if ((s.charAt(left) + 32 - 'a') % 32 != (s.charAt(right) + 32 - 'a') % 32) {
                return false;
            } else {
                left++;
                right--;
            }
        }
        return true;
    }

    public boolean isChar(char c) {
        return ('0' <= c && c <= '9') || ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z');
    }

    /**
     * 回文子串
     * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
     * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
     */
    public static int numPalindrome(String s) {
        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            //回文串长度为奇数
            num += count(s, i, i);
            //回文串长度为偶数
            num += count(s, i, i + 1);
        }
        return num;
    }

    /**
     * 回文对
     * 给定一组唯一的单词，
     * 找出所有不同 的索引对(i, j)，使得列表中的两个单词，
     * words[i] + words[j] ，可拼接成回文串。
     */
    public static List<List<Integer>> palindromePairs(String[] words) {
        int n = words.length;
        // 构建字符串逆序字典，用于下面查找相反部分字符串
        Map<String, Integer> indices = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            indices.put(new StringBuffer(words[i]).reverse().toString(), i);
        }

        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String word = words[i];
            for (int j = 0; j <= word.length(); j++) {
                // 若当前字符串右部分为回文
                // 寻找与左部分相反的字符串
                if (isPalindrome(word, j, word.length() - 1)) {
                    int leftId = indices.getOrDefault(word.substring(0, j), -1);
                    if (leftId != -1 && leftId != i) {
                        res.add(Arrays.asList(i, leftId));
                    }
                }
                // 若当前字符串左部分为回文
                // 寻找与右部分相反的字符串
                if (j != 0 && isPalindrome(word, 0, j - 1)) {
                    int rightId = indices.getOrDefault(word.substring(j), -1);
                    if (rightId != -1 && rightId != i) {
                        res.add(Arrays.asList(rightId, i));
                    }
                }
            }
        }
        return res;
    }

    private static int count(String s, int start, int end) {
        int num = 0;
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            num++;
            start--;
            end++;
        }
        return num;
    }

    @Data
    static class Index {
        int index, len;
    }

    @Data
    public static class ListNode {
        int val;
        ListNode next;

        public ListNode(int x) {
            val = x;
        }
    }
}